package 我的Java学习_算法基础.day_05;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 例：
 * Input:
 * 3
 * aaa
 * Output:
 *          2 2
 *          3 3
 *          长度 重复次数
 */
public class _088_next数组的例题 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<String> list = new ArrayList<>();
        while(true){
            int n = sc.nextInt();
            if(n==0){
                break;
            }
            String s = sc.next();
            list.add(s);
        }
        for(int j = 0;j<list.size();j++){
            String s = list.get(j);
            int[] next = next(s);
            System.out.println("Test case #"+(j+1));
            for(int i =2;i<next.length;i++){//i是字符长度
                int k = next[i];
                int t = i-k;//周期
                if(i%t ==0&& i/t>1){//满周期、至少包含两个周期
                    System.out.println(i+" "+i/t);
                }
            }
            System.out.println();
        }
    }
    private static int[] next(String s){
        if(s==null||s.length()==0) return null;
        int[] next = new int[s.length()+1];
        char[] p = s.toCharArray();
        next[0] = -1;
        if(s.length()==1){
            return next;
        }
        next[1] = 0;

        int j = 1;
        int k = next[j];//看看j的最长匹配前缀在哪
        while(j<s.length()){
            //现在要推出next[j+1]，检查j和k位置上的关系即可
            if(k<0||p[j]==p[k]){
                next[++j]=++k;
            }else{
                k=next[k];
            }
        }
        return next;
    }
}
